﻿/*

The MIT License

Copyright (c) 2010 Cartesian Analytics, Inc. 

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;

namespace Pipra.Math.Geometry
{
    /// <summary>
    /// A collection of points representing a closed boundary edge of a polygon.
    /// </summary>
    /// <remarks>
    /// <list type="bullet">
    /// <item><term>Point Winding and the <see cref="Pipra.Math.Geometry.Ring2.Hole"/> Property</term>
    /// <description>
    /// It is good practice to set the <see cref="Pipra.Math.Geometry.Ring2.Hole"/> property to true or false for interoperability purposes.
    /// Winding must be taken into account when operating on these rings and should either be explicity set before use of the ring or the <see cref="Pipra.Math.Geometry.Ring2.Hole"/> property should be set and used.
    /// <see cref="Pipra.Math.Geometry.Ring2.ForceFillWinding"/> can be used to enforce a specific winding for your needs after setting the <see cref="Pipra.Math.Geometry.Ring2.Hole"/> property of the ring.
    /// </description>
    /// </item>
    /// <item><term>Redundant End Points</term>
    /// <description>
    /// This ring class does not require the storage of matching start and end points and some algorithms may remove or disregard the end point or may need to compensate for a missing redundant end point.
    /// It is prefered that a ring does not have a redundant start and end point.
    /// This means that a triangle may be defined by 3 unique points instead of 4 points where the start and end are equivilant.
    /// This also means that a triangle may be defined by 4 points where the start and end are equivilant.
    /// The final segment of the ring will stretch from the last point to the first point.
    /// Even when the first and last point are equal there will be a final segment of magnitude 0.
    /// When matching start and end points are required for interoperability, the redundant end point becomes the responsibility of that functionality.
    /// You may use <see cref="Pipra.Math.Geometry.Ring2.HasRedundantEndPoint"/> to determine if the ring contains a redundant end point.
    /// </description>
    /// </item>
    /// </list>
    /// </remarks>
    /// <seealso cref="Pipra.Math.Geometry.Point2"/>
    /// <seealso cref="Pipra.Math.Geometry.Segment2"/>
    /// <seealso cref="Pipra.Math.Geometry.PointWinding"/>
    public class Ring2 :
        Collection<Point2>,
        IPlanarGeometry<double>,
        IHasMagnitude<double>,
        IHasArea<double>,
        IEquatable<Ring2>,
        IIntersectable<Point2>,
        IHasDistance<double, Point2>,
        IContainable<Mbr>,
        ICloneable,
        ISelfIntersectable
    {

        public static bool operator ==(Ring2 a, Ring2 b)
        {
            return ReferenceEquals(a, b) || (!ReferenceEquals(null, a) && a.Equals(b));
        }

        public static bool operator !=(Ring2 a, Ring2 b)
        {
            return !ReferenceEquals(a, b) && (ReferenceEquals(null, a) || !a.Equals(b));
        }

        private bool? _hole;
        /// <summary>
        /// Constructs a ring with no points.
        /// </summary>
        public Ring2() : this(null,null) { }
        /// <summary>
        /// Constructs a ring with no points while expecting the given number of points at a later time.
        /// </summary>
        /// <param name="expectedCapacity">The expected capacity of the ring.</param>
        public Ring2(int expectedCapacity) : this(null, new List<Point2>(expectedCapacity)) { }
        /// <summary>
        /// Constructs a ring that will be explicitly set as a hole or fill.
        /// </summary>
        /// <param name="hole">True to flag as a hole, false to flag as a fill.</param>
        public Ring2(bool hole) : this(hole, null) { }
        /// <summary>
        /// Constructs a ring with no points while expecting the given number of points at a later time with the hole/fill property explicitly set.
        /// </summary>
        /// <param name="hole">True to flag as a hole, false to flag as a fill.</param>
        /// <param name="expectedCapacity">The expected capacity of the ring.</param>
        public Ring2(bool hole, int expectedCapacity) : this(hole, new List<Point2>(expectedCapacity)) { }
        /// <summary>
        /// Constructs a ring with the given points.
        /// </summary>
        /// <param name="points">The ordered set of points that define the ring.</param>
        public Ring2(IEnumerable<Point2> points) : this(null, null == points ? null : new List<Point2>(points)) { }
        /// <summary>
        /// Constructs a ring with the given points with the hole/fill property explicitly set.
        /// </summary>
        /// <param name="points">The ordered set of points that define the ring.</param>
        /// <param name="hole">True to flag as a hole, false to flag as a fill.</param>
        public Ring2(IEnumerable<Point2> points, bool hole) : this(hole,null == points ? null : new List<Point2>(points)) { }

        private Ring2(bool? hole, List<Point2> points)
            : base(points ?? new List<Point2>())
        {
            _hole = hole;
        }

        /// <summary>
        /// Used to mark a ring as being a hole or fill.
        /// </summary>
        /// <remarks>
        /// <list type="table">
        /// <item><term>True</term><description>The ring is a hole.</description></item>
        /// <item><term>False</term><description>The ring is a fill.</description></item>
        /// <item><term>null</term><description>It is unknown if the ring is a hole or fill.</description></item>
        /// </list>
        /// </remarks>
        public bool? Hole
        {
            get
            {
                return _hole;
            }
            set
            {
                _hole = value;
            }
        }

        /// <summary>
        /// Determines if the first point and the last point in this ring are equal.
        /// </summary>
        public bool HasRedundantEndPoint
        {
            get
            {
                int lasti = Count - 1;
                return (lasti >= 2 && this[0].Equals(this[lasti]));
            }
        }

        /// <summary>
        /// Determines the number of segments within this ring.
        /// </summary>
        /// <remarks>There can never be two segments.</remarks>
        public int SegmentCount
        {
            get
            {
                var c = Count;
                return (
                    (c >= 3)
                    ? c
                    : (
                        (0 == c)
                        ? 0
                        : (c - 1)
                    )
                );
            }
        }

        /// <summary>
        /// Creates a segment at the specified index within this ring.
        /// </summary>
        /// <param name="i">The segment number to create.</param>
        /// <returns>A segment.</returns>
        /// <exception cref="ArgumentOutOfRangeException">Param <paramref name="i"/> must be positive and less than the number of segments in this ring.</exception>
        public Segment2 GetSegment(int i)
        {
            if (i < 0 || i >= SegmentCount)
            {
                throw new ArgumentOutOfRangeException("i", "Param i must be positive and less than the number of segments in this ring.");
            }
            return new Segment2(
                this[i],
                this[((i + 1) >= Count) ? 0 : (i + 1)]
            );
        }

        /// <summary>
        /// Determines the perimeter of the ring.
        /// </summary>
        /// <returns>The perimeter of the ring.</returns>
        public double GetMagnitude()
        {
            int lasti = Count - 1;
            if (lasti > 1)
            {
                double sum = this[lasti].Distance(this[0]);
                for (int i = 0, nexti = 1; i < lasti; i = nexti++)
                {
                    sum += this[i].Distance(this[nexti]);
                }
                return sum;
            }
            return (1 == lasti) ? this[0].Distance(this[1]) : 0.0;
        }
        double IHasMagnitude<double>.GetMagnitudeSquared()
        {
            double m = GetMagnitude();
            return m * m;
        }

        private double GetAreaSumValue()
        {
            if (SegmentCount < 3)
            {
                return 0;
            }
            double sum = 0;
            int lasti = Count - 1;
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 a = this[i];
                Point2 b = this[nexti];
                sum += (a.X * b.Y) - (b.X * a.Y);
            }
            return sum;
        }

        /// <summary>
        /// Calculates the area of the interior of the ring.
        /// </summary>
        /// <returns>The area of the interior of the ring.</returns>
        /// <remarks>
        /// The area of a hole and a fill made of the same points will both have the same magnitude but a different sign
        /// <list type="table">
        /// <item><term>Fill</term><description>Will return the area of the interor of the ring boundary.</description></item>
        /// <item><term>Hole</term><description>Will return the negative area of the interor of the ring boundary.</description></item>
        /// <item><term>Undefined</term><description>CounterClockwise point ordering will be treated as a fill, Clockwise ordering will be treated as a hole, and Unknown ordering will have an area of 0.</description></item>
        /// </list>
        /// </remarks>
        public double GetArea()
        {
            double sum = GetAreaSumValue() * 0.5;
            if(_hole.HasValue)
            {
                sum = System.Math.Abs(sum);
                if(true == _hole)
                {
                    return -sum;
                }
            }
            return sum;
        }

        /// <summary>
        /// Determines the centroid of the ring.
        /// </summary>
        /// <returns>the centroid of the ring.</returns>
        public Point2 GetCentroid()
        {
            int lasti = Count - 1;
            if (lasti > 1)
            {
                double sumValue = 0;
                double xSum = 0;
                double ySum = 0;
                for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
                {
                    Point2 a = this[i];
                    Point2 b = this[nexti];
                    double f = (a.X * b.Y) - (b.X * a.Y);
                    xSum += (a.X + b.X) * f;
                    ySum += (a.Y + b.Y) * f;
                    sumValue += f;
                }
                if (0 != sumValue)
                {
                    sumValue = sumValue * 3.0;
                    return new Point2(xSum / sumValue, ySum / sumValue);
                }
                return this[0];
            }
            return (
                0 == lasti
                ? this[0]
                : (
                    1 == lasti
                    ? new Point2((this[0].X + this[1].X) * 0.5, (this[0].Y + this[1].Y) * 0.5)
                    : Point2.Invalid
                )
            );
        }

        IPoint2<double> IHasPlanarCentroid<double>.GetCentroid()
        {
            return GetCentroid();
        }

        /// <summary>
        /// Determines the point winding of the ring.
        /// </summary>
        /// <remarks><list type="table">
        /// <item><term>Clockwise</term><description>The points in the ring are specified in clockwise order.</description></item>
        /// <item><term>CounterClockwise</term><description>The points in the ring are specified in counter clockwise order.</description></item>
        /// <item><term>Unknown</term><description>The order of the points in the ring can not be determined.</description></item>
        /// </list></remarks>
        /// <returns>The point winding of the ring.</returns>
        public PointWinding DetermineWinding()
        {
            double areaSum = GetAreaSumValue();
            return (
                (0 == areaSum || Double.IsNaN(areaSum))
                ? PointWinding.Unknown
                : (
                    0 > areaSum
                    ? PointWinding.Clockwise
                    : PointWinding.CounterClockwise
                )
            );
        }

        /// <summary>
        /// Forces the fill winding of the points within the ring.
        /// </summary>
        /// <param name="desiredWinding">The desired winding order to specify a fill region.</param>
        /// <remarks>
        /// If the current <see cref="Pipra.Math.Geometry.Ring2.Hole"/> property of this ring is null then the Hole property will be set if possible to the value corresponding to the given fill point winding.
        /// If the current <see cref="Pipra.Math.Geometry.Ring2.Hole"/> property of this ring is true or false then the points will be ordered if possible in a way to match the given fill point winding and hole property.
        /// <list type="bullet">
        /// <item><term>Example 1</term><description>Hole is initially null and points are in CounterClockwise order. If <paramref name="desiredWinding"/> is Clockwise then Hole will then be set to True and the Points will not be changed.</description></item>
        /// <item><term>Example 2</term><description>Hole is false and points are in Clockwise order. If <paramref name="desiredWinding"/> is CounterClockwise then the order of the points in the Ring will be reversed.</description></item>
        /// </list>
        /// </remarks>
        public void ForceFillWinding(PointWinding desiredWinding)
        {
            if (PointWinding.Unknown == desiredWinding)
            {
                throw new ArgumentException("DesiredWinding can not be Unknown.", "desiredWinding");
            }
            PointWinding currentWinding = DetermineWinding();
            if (PointWinding.Unknown == currentWinding) return;
            if (null == _hole)
            {
                _hole = (currentWinding != desiredWinding);
            }
            else
            {
                if (
                    (currentWinding != desiredWinding && false == _hole)
                    ||
                    (currentWinding == desiredWinding && true == _hole)
                    )
                {
                    int halfCount = Count;
                    int lasti = halfCount - 1;
                    halfCount /= 2;
                    for (int i = 0, i2 = lasti; i < halfCount; i2 = lasti - (++i))
                    {
                        var swap = this[i];
                        this[i] = this[i2];
                        this[i2] = swap;
                    }
                }
            }
        }

        /// <summary>
        /// Generates a line string for the boundary of this ring.
        /// </summary>
        /// <returns>The boundary of this ring.</returns>
        public LineString2 GenerateLineString()
        {
            LineString2 ls = new LineString2(this);
            if (Count > 2 && !HasRedundantEndPoint)
            {
                ls.Add(this[0]);
            }
            return ls;
        }

        /// <summary>
        /// Calculates a MBR encapsulating all points within this ring.
        /// </summary>
        /// <returns>A MBR encapsulating all points within this ring.</returns>
        public Mbr GetMbr()
        {
            if (Count > 1)
            {
                Mbr result = new Mbr(this[0], this[1]);
                for (int i = 2; i < Count; i++)
                {
                    result = result.Union(this[i]);
                }
                return result;
            }
            return (1 == Count) ? new Mbr(this[0]) : Mbr.Invalid;
        }
        IMbr<double> IHasMbr<double>.GetMbr()
        {
            return GetMbr();
        }

        /// <summary>
        /// Determines the distance from this ring to the given point <paramref name="p"/>.
        /// </summary>
        /// <param name="p">The point to determind the distance to.</param>
        /// <returns>The distance from this ring to the given point <paramref name="p"/>.</returns>
        /// <remarks>
        /// The distance will be 0 when the ring is a fill and the point lies within the boundary, when the ring is a hole and the point lies outside of the boundary, or when the point lies on the boundary.
        /// </remarks>
        public double Distance(Point2 p)
        {
            return System.Math.Sqrt(DistanceSquared(p));
        }
        /// <summary>
        /// Determines the distance from this ring to the given point <paramref name="p"/>.
        /// </summary>
        /// <param name="p">The point to determind the distance to.</param>
        /// <returns>The distance from this ring to the given point <paramref name="p"/>.</returns>
        /// <remarks>
        /// The distance will be 0 when the ring is a fill and the point lies within the boundary, when the ring is a hole and the point lies outside of the boundary, or when the point lies on the boundary.
        /// </remarks>
        public double Distance(IPoint2<double> p)
        {
            return Distance(new Point2(p));
        }
        /// <summary>
        /// Determines the squared distance from this ring to the given point <paramref name="p"/>.
        /// </summary>
        /// <param name="p">The point to determind the squared distance to.</param>
        /// <returns>The squared distance from this ring to the given point <paramref name="p"/>.</returns>
        /// <remarks>
        /// The squared distance will be 0 when the ring is a fill and the point lies within the boundary, when the ring is a hole and the point lies outside of the boundary, or when the point lies on the boundary.
        /// </remarks>
        public double DistanceSquared(Point2 p)
        {
            int lasti = Count - 1;
            if (lasti > 1)
            {
                if (Intersects(p, false))
                {
                    return 0;
                }
                double d = Segment2.DistanceSquared(this[lasti], this[0], p);
                for (int i = 0, nexti = 1; i < lasti; i = nexti++)
                {
                    d = System.Math.Min(d, Segment2.DistanceSquared(this[i], this[nexti], p));
                }
                return d;
            }
            return (
                0 == lasti
                ? this[0].DistanceSquared(p)
                : (
                    (1 == lasti)
                    ? Segment2.DistanceSquared(this[0], this[1], p)
                    : Double.NaN
                )
            );
        }
        /// <summary>
        /// Determines the squared distance from this ring to the given point <paramref name="p"/>.
        /// </summary>
        /// <param name="p">The point to determind the squared distance to.</param>
        /// <returns>The squared distance from this ring to the given point <paramref name="p"/>.</returns>
        /// <remarks>
        /// The squared distance will be 0 when the ring is a fill and the point lies within the boundary, when the ring is a hole and the point lies outside of the boundary, or when the point lies on the boundary.
        /// </remarks>
        public double DistanceSquared(IPoint2<double> p)
        {
            return DistanceSquared(new Point2(p));
        }

        /// <summary>
        /// Determines if the point intersects the filled region or boundary of this ring.
        /// </summary>
        /// <param name="p">The point to test.</param>
        /// <returns>True if the point intersects the filled region or boundary of this ring.</returns>
        /// <remarks>
        /// If this ring is a fill the filled region lies within the boundary but when the ring is a hole the filled region lies outside the ring boundary.
        /// </remarks>
        public bool Intersects(Point2 p)
        {
            return Intersects(p, true);
        }
        /// <summary>
        /// Determines if the point intersects the filled region or boundary of this ring.
        /// </summary>
        /// <param name="p">The point to test.</param>
        /// <returns>True if the point intersects the filled region or boundary of this ring.</returns>
        /// <remarks>
        /// If this ring is a fill the filled region lies within the boundary but when the ring is a hole the filled region lies outside the ring boundary.
        /// </remarks>
        public bool Intersects(IPoint2<double> p)
        {
            return Intersects(new Point2(p));
        }

        internal int IntersectionPosXRayCount(Point2 p)
        {
            int lasti = Count - 1;
            int isecCount = 0;
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 a = this[i];
                Point2 b = this[nexti];
                if (
                    (
                        p.Y < b.Y
                        &&
                        a.Y <= p.Y
                        &&
                        (
                            ((p.Y - a.Y) * (b.X - a.X))
                            >
                            ((p.X - a.X) * (b.Y - a.Y))
                        )
                    )
                    ||
                    (
                        p.Y < a.Y
                        &&
                        b.Y <= p.Y
                        &&
                        (
                            ((p.Y - a.Y) * (b.X - a.X))
                            <
                            ((p.X - a.X) * (b.Y - a.Y))
                        )
                    )
                )
                {
                    isecCount++;
                }
            }
            return isecCount;
        }

        internal bool NonIntersectingWithin(Ring2 testContainer)
        {

            //bool isWithinRingMbr = GetMbr().Within(testContainer.GetMbr());
            if (testContainer.Hole.HasValue && testContainer.Hole.Value)
            {
                // container is a hole, we want this boundary not within container's
                if (!GetMbr().Within(testContainer.GetMbr()))
                {
                    bool mayHaveIt = false;
                    foreach (Point2 p in this)
                    {
                        int res = testContainer.AdvancedIntersectionTest(p);
                        if (res == 1)
                        {
                            mayHaveIt = true;
                        }
                        else if (res == -1)
                        {
                            return false;
                        }
                    }
                    return mayHaveIt;
                }
                return false;
            }
            // container is a fill, we want to be within the container's boundary
            if (GetMbr().Within(testContainer.GetMbr()))
            {
                bool mayHaveIt = false;
                foreach (Point2 p in this)
                {
                    int res = testContainer.AdvancedIntersectionTest(p);
                    if (res == 1)
                    {
                        mayHaveIt = true;
                    }
                    else if (res == -1)
                    {
                        return false;
                    }
                }
                return mayHaveIt;
            }
            return false;

        }

        /// <summary>
        /// Advanced intersection testing.
        /// </summary>
        /// <param name="p"></param>
        /// <returns>0 for bondary, 1 for within, -1 for outside</returns>
        internal int AdvancedIntersectionTest(Point2 p)
        {
            int lasti = Count - 1;
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 a = this[i];
                Point2 b = this[nexti];
                if (Segment2.Intersects(a, b, p))
                {
                    return 0;
                }
            }
            return Intersects(p, true) ? 1 : -1;
        }

        internal int IntersectionPosYRayCount(Point2 p)
        {
            int lasti = Count - 1;
            int isecCount = 0;
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 a = this[i];
                Point2 b = this[nexti];
                if (
                    (
                        -p.X < -b.X
                        &&
                        -a.X <= p.X
                        &&
                        (
                            (((-p.X) - (-a.X)) * (b.Y - a.Y))
                            >
                            ((p.Y - a.Y) * ((-b.X) - (-a.X)))
                        )
                    )
                    ||
                    (
                        (-p.X) < (-a.X)
                        &&
                        (-b.X) <= (-p.X)
                        &&
                        (
                            (((-p.X) - (-a.X)) * (b.Y - a.Y))
                            <
                            ((p.Y - a.Y) * ((-b.X) - (-a.X)))
                        )
                    )
                )
                {
                    isecCount++;
                }
            }
            return isecCount;
        }

        internal int IntersectionsRayCount(Ray2 r)
        {
            int lasti = Count - 1;
            int isecCount = 0;
            Vector2 normal = r.Direction.GetNormalized();
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 a = this[i];
                Point2 b = this[nexti];
                if (!b.Equals(r.P) && r.Intersects(b))
                {
                    int nextNexti = nexti + 1;
                    if (nextNexti > lasti)
                    {
                        nextNexti = 0;
                    }
                    Vector2 v1 = this[nexti].Difference(this[i]);
                    Vector2 v2 = this[nextNexti].Difference(this[nexti]);
                    if (0 == normal.Cross(v2) && 0 != normal.Cross(v1))
                    {
                        isecCount++;
                    }
                }
                else if (!a.Equals(r.P) && r.Intersects(a))
                {
                    int previ = i - 1;
                    if (previ < 0)
                    {
                        previ = lasti;
                    }
                    Vector2 v1 = this[i].Difference(this[previ]);
                    Vector2 v2 = this[nexti].Difference(this[i]);
                    double cross1 = normal.Cross(v1);
                    double cross2 = normal.Cross(v2);
                    if (
                        (0 == cross1 && 0 != cross2)
                        || (cross1 < 0 && cross2 < 0)
                        || (cross1 > 0 && cross2 > 0)
                    )
                    {
                        isecCount++;
                    }

                }
                else if (!Segment2.Intersects(a, b, r.P) && r.Intersects(new Segment2(a, b)))
                {
                    isecCount++;
                }
            }
            return isecCount;
        }

        internal bool Intersects(Point2 p, bool garanteeEdge)
        {
            int lasti = Count - 1;
            if (2 <= lasti)
            {
                int isecCount = IntersectionPosXRayCount(p);
                if (isecCount > 0)
                {
                    return (isecCount % 2) == (_hole.Equals(true) ? 0 : 1);
                }
                if (_hole.Equals(true))
                {
                    return true;
                }
                if (garanteeEdge)
                {
                    for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
                    {
                        if (Segment2.Intersects(this[i], this[nexti], p))
                        {
                            return true;
                        }
                    }
                }
                return false;
            }
            return (
                0 == lasti
                ? this[0].Equals(p)
                : 1 == lasti && Segment2.Intersects(this[0], this[1], p)
            );
        }

        internal bool SegmentCrossesBoundary(Segment2 s)
        {
            return SegmentCrossesBoundary(s.A, s.B);
        }

        internal bool SegmentCrossesBoundary(Point2 a, Point2 b)
        {
            double dymcy = b.Y - a.Y;
            double dxmcx = b.X - a.X;
            int lasti = Count - 1;
            for (int i = lasti, nexti = 0; nexti <= lasti; i = nexti++)
            {
                Point2 c = this[i];
                Point2 d = this[nexti];
                double bxmax = d.X - c.X;
                double bymay = d.Y - c.Y;
                double den = (dymcy * bxmax) - (dxmcx * bymay);
                if (0 != den)
                {
                    double aymcy = c.Y - a.Y;
                    double axmcx = c.X - a.X;
                    double na = (dxmcx * aymcy) - (dymcy * axmcx);
                    double nb = (bxmax * aymcy) - (bymay * axmcx);
                    if (
                        (den < 0)
                        ? (na <= 0 && na >= den && nb <= 0 && nb >= den)
                        : (na >= 0 && na <= den && nb >= 0 && nb <= den)
                    )
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        internal double FindNearestSegment(Point2 location, out int segmentIndex)
        {
            if (0 == Count)
            {
                segmentIndex = 0;
                return Double.NaN;
            }
            if (1 == Count)
            {
                segmentIndex = 0;
                return this[0].Distance(location);
            }

            int nearestVertexIndex = 0;
            double bestPointDistSq = this[0].DistanceSquared(location);
            for (int i = 1; i < Count; i++)
            {
                double curDistSq = this[i].DistanceSquared(location);
                if (curDistSq < bestPointDistSq)
                {
                    nearestVertexIndex = i;
                    bestPointDistSq = curDistSq;
                }
            }

            if (Count < 3)
            {
                segmentIndex = 0;
                return this[nearestVertexIndex].Distance(location);
            }

            int lasti = Count - 1;
            int nearestSegmentIndex = 0;
            double bestSegDistSq = Segment2.DistanceSquared(this[lasti], this[0], location);
            for (int i = 0, nexti = 1; i < lasti; i = nexti++)
            {
                double curDistSq = Segment2.DistanceSquared(this[i], this[nexti], location);
                if (curDistSq < bestSegDistSq)
                {
                    nearestSegmentIndex = nexti;
                    bestSegDistSq = curDistSq;
                }
            }
            if (bestPointDistSq <= bestSegDistSq)
            {
                // add by point
                int prevVertexIndex = (nearestVertexIndex == 0) ? lasti : nearestVertexIndex - 1;
                int nextVertexIndex = (nearestVertexIndex == lasti) ? 0 : nearestVertexIndex + 1;
                Point2 prevVertex = this[prevVertexIndex];
                Point2 nextVertex = this[nextVertexIndex];
                Point2 nearestVertex = this[nearestVertexIndex];
                Vector2 nearestVector = location.Difference(nearestVertex).GetNormalized();
                Vector2 prevVector = prevVertex.Difference(location).GetNormalized();
                Vector2 nextVector = nextVertex.Difference(location).GetNormalized();
                double dotPrev = nearestVector.Dot(prevVector);
                double dotNext = nearestVector.Dot(nextVector);
                segmentIndex = dotPrev > dotNext ? nearestVertexIndex : nextVertexIndex;
                return System.Math.Sqrt(bestPointDistSq);
            }
            // add by segment
            segmentIndex = nearestSegmentIndex;
            return System.Math.Sqrt(bestSegDistSq);
        }

        internal double FindNearestVertex(Point2 location, double tolerance, out int bestIndex)
        {
            bestIndex = -1;
            double bestDistSq = Double.PositiveInfinity;
            for (int i = 0; i < Count; i++)
            {
                double curDistSq = this[i].DistanceSquared(location);
                if (curDistSq < bestDistSq)
                {
                    bestIndex = i;
                    bestDistSq = curDistSq;
                }
            }
            double dist;
            if (bestIndex >= 0 && (dist = System.Math.Sqrt(bestDistSq)) <= tolerance)
            {
                return dist;
            }
            bestIndex = -1;
            return Double.NaN;
        }

        /// <summary>
        /// Creates an identical ring.
        /// </summary>
        /// <returns>A ring.</returns>
        public Ring2 Clone()
        {
            return new Ring2(_hole,new List<Point2>(this));
        }
        object ICloneable.Clone()
        {
            return Clone();
        }

        /// <summary>
        /// Returns a <see cref="System.String"/> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="System.String"/> that represents this instance.
        /// </returns>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder(String.Concat("Ring, ", Count, "point"));
            if (1 != Count)
            {
                sb.Append('s');
            }
            if (_hole.HasValue)
            {
                sb.Append(", ");
                sb.Append(_hole.Value ? "hole" : "fill");
            }
            if (Count < 4)
            {
                for (int i = 0; i < Count; i++)
                {
                    sb.Append(' ');
                    sb.Append(this[i]);
                }
            }
            return sb.ToString();
        }

        public override bool Equals(object obj)
        {
            return null != obj
                && (
                    (obj is Ring2 && Equals(obj as Ring2))
                )
            ;
        }

        public override int GetHashCode()
        {
            return GetMbr().GetHashCode() & 929283730;
        }

        /// <summary>
        /// Indicates whether the current object is equal to another object of the same type.
        /// </summary>
        /// <returns>
        /// true if the current object is equal to the <paramref name="other"/> parameter; otherwise, false.
        /// </returns>
        /// <param name="other">An object to compare with this object.</param>
        public bool Equals(Ring2 other)
        {
            if (ReferenceEquals(this, other))
            {
                return true;
            }
            if (ReferenceEquals(null, other))
            {
                return false;
            }
            if (Count == other.Count && _hole.Equals(other._hole))
            {
                for (int i = 0; i < Count; i++)
                {
                    if (!this[i].Equals(other[i]))
                    {
                        return false;
                    }
                }
                return true;
            }
            return false;
        }

        /// <summary>
        /// Determines if the given MBR contains this ring boundary.
        /// </summary>
        /// <param name="mbr">The MBR to test.</param>
        /// <returns>True if this ring boundary is within the given MBR.</returns>
        public bool Within(Mbr mbr)
        {
            return GetMbr().Within(mbr);
        }
        /// <summary>
        /// Determines if the given MBR contains this ring boundary.
        /// </summary>
        /// <param name="mbr">The MBR to test.</param>
        /// <returns>True if this ring boundary is within the given MBR.</returns>
        public bool Within(IMbr<double> mbr)
        {
            return GetMbr().Within(mbr);
        }

        /// <summary>
        /// Determines if this ring boundary is self-intersecting.
        /// </summary>
        /// <returns>True if self-intersecting.</returns>
        public bool IsSelfIntersecting()
        {
            throw new NotImplementedException();
        }
    }
}
